class Solution(object):
    def racecar(self, target):
        start_st = {(0, 1)}
        a_st = {(0, 1)}
        dist = 0
        while True:
            dist += 1
            next_start = set()
            for pos, v in a_st:
                if pos + v == target:
                    return dist
                if (pos + v, 2 * v) not in start_st:
                    start_st.add((pos + v, 2 * v))
                    next_start.add((pos + v, 2 * v))
                if (pos, - v // abs(v)) not in start_st:
                    start_st.add((pos, - v // abs(v)))
                    next_start.add((pos, - v // abs(v)))
            a_st = next_start


data = Solution()
target = 3
print(data.racecar(target))
